#!/usr/bin/python3
"""HeapSort Implements"""

import math

def heapsort(arrayA):
    build_max_heap(arrayA)
    heap_size = len(arrayA)
    for i in range(len(arrayA), 1, -1):
        exchange(arrayA, python_index(1), python_index(i))
        heap_size -= 1
        max_heapify(arrayA, 1, heap_size)
        

def build_max_heap(arrayA):
    for i in range(math.floor(len(arrayA)/2), 0, -1):
        max_heapify(arrayA, i)

        
def max_heapify(arrayA, index, heap_size=None):
    if not heap_size:
        heap_size = len(arrayA)
    left = _left(index)
    right = _right(index)
    if left <= heap_size and arrayA[python_index(left)] > arrayA[python_index(index)]:
        largest = left
    else:
        largest = index

    if right <= heap_size and arrayA[python_index(right)] > arrayA[python_index(largest)]:
        largest = right

    if largest != index:
        exchange(arrayA, python_index(index), python_index(largest))
        max_heapify(arrayA, largest, heap_size)


def python_index(index):
    """ 算法导论这本书中， 数组的最小下标为1， 与计算机的常规不同， 这里进行转化。
        为什么转换left， right公式呢， 速率更好不是， 这里为了与算法导论保持一直. 
         """
    return index - 1;

def exchange(arrayA, indexA, indexB):
    tmp = arrayA[indexA]
    arrayA[indexA] = arrayA[indexB]
    arrayA[indexB] = tmp

    
def p_parent(index):
    return math.floor(index/2)


def _left(index):
    return 2 * index


def _right(index):
    return 2 * index + 1


def test_build_max_heap():
    test_array = [4,1,3,2,16,9,10,14,8,7]
    build_max_heap(test_array)
    print(test_array)
    assert test_array[0] == 16
    assert test_array[4] == 7
    assert test_array[7] == 2
    assert test_array[9] == 1


if __name__=='__main__':
    test_array = [4,1,3,2,16,9,10,14,8,7]
    heapsort(test_array)
    print(test_array)
